#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <set>
using namespace std;
class Solution
{
public:
    int partition(vector<int> &nums, int l, int r)
    {
        if (l >= r)
            return r;
        swap(nums[(l + r) / 2], nums[r]);
        int i = l - 1, pivot = nums[r];
        for (int j = l; j < r; ++j)
        {
            if (nums[j] > pivot)
                swap(nums[++i], nums[j]);
        }
        swap(nums[i + 1], nums[r]);
        return i + 1; // pivot的位置
    }
    int selectK(vector<int> &nums, int l, int r, int k)
    {
        if (l == r)
            return nums[l];
        int pivotPos = partition(nums, l, r);
        if (k < pivotPos)
            return selectK(nums, l, pivotPos - 1, k);
        else if (pivotPos < k)
            return selectK(nums, pivotPos + 1, r, k);
        else
            return nums[pivotPos];
    }
    int findKthLargest(vector<int> &nums, int k)
    {
        return selectK(nums, 0, nums.size() - 1, k);
    }
};